package leetcode

// https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
func search(nums []int, target int) int {
	left := leftBound(nums, target)
	if left == -1 {
		return 0
	}
	return rightBound(nums, target) - left + 1
}

func leftBound(nums []int, target int) int {
	left, right := 0, len(nums)
	for mid := left + (right-left)/2; left < right; mid = left + (right-left)/2 {
		if nums[mid] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if left >= len(nums) || nums[left] != target {
		return -1
	}
	return left
}

func rightBound(nums []int, target int) int {
	left, right := 0, len(nums)
	for mid := left + (right-left)/2; left < right; mid = left + (right-left)/2 {
		if nums[mid] <= target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	if left-1 < 0 || nums[left-1] != target {
		return -1
	}
	return left - 1
}

// [5,7,7,8,8,10] 8
// func main() {
// 	array, target := []int{5, 7, 7, 8, 8, 10}, 5
// 	fmt.Print(left_bound(array, target), " ")
// 	fmt.Println(right_bound(array, target))
// 	fmt.Println(search(array, target))
// }
